class Solution
{
public:
    // 超时
    long long minimumCost(string source, string target, vector<string> &original, vector<string> &changed, vector<int> &cost)
    {
        unordered_map<string, int> strToNum;
        vector<string> numToStr;
        int id = 0;
        for (auto &str : original)
        {
            if (!strToNum.count(str))
            {
                strToNum[str] = id++;
                numToStr.push_back(str);
            }
        }
        for (auto &str : changed)
        {
            if (!strToNum.count(str))
            {
                strToNum[str] = id++;
                numToStr.push_back(str);
            }
        }
        int strConut = id;
        vector<vector<int>> graph(strConut, vector<int>(strConut, INT_MAX));
        for (int i = 0; i < original.size(); i++)
        {
            graph[strToNum[original[i]]][strToNum[changed[i]]] = min(graph[strToNum[original[i]]][strToNum[changed[i]]], cost[i]);
        }

        vector<vector<int>> dists(strConut, vector<int>(strConut, INT_MAX));
        auto dijkstra = [&](int start, int end)
        {
            if (start == end)
            {
                return 0;
            }
            if (dists[start][end] != INT_MAX)
            {
                return dists[start][end];
            }
            vector<int> dist(strConut, INT_MAX);
            vector<bool> visited(strConut, false);
            dist[start] = 0;
            for (int i = 0; i < strConut; i++)
            {
                int minDist = INT_MAX;
                int minIndex = -1;
                for (int j = 0; j < strConut; j++)
                {
                    if (!visited[j] && dist[j] < minDist)
                    {
                        minDist = dist[j];
                        minIndex = j;
                    }
                }
                if (minIndex == -1)
                {
                    break;
                }
                visited[minIndex] = true;
                for (int j = 0; j < strConut; j++)
                {
                    if (graph[minIndex][j] != INT_MAX)
                    {
                        dist[j] = min(dist[j], dist[minIndex] + graph[minIndex][j]);
                    }
                }
            }
            dists[start][end] = dist[end];
            return dist[end];
        };

        for (int i = 0; i < strConut; i++)
        {
            for (int j = 0; j < strConut; j++)
            {
                dists[i][j] = dijkstra(i, j);
            }
        }

        int n = source.size();
        vector<unordered_set<long long>> canMap(n);
        for (string &str : original)
        {
            long long pos = 0;
            int strId = strToNum[str];
            while (true)
            {
                pos = source.find(str, pos);
                if (pos == string::npos)
                {
                    break;
                }
                for (int i = pos; i < pos + str.size(); i++)
                {
                    canMap[i].insert((pos << 32) | strId);
                }
                pos++;
            }
        }

        function<long long(int)> dfs = [&](int begin) -> long long
        {
            if (begin == n)
            {
                return 0;
            }

            int i = begin;
            while (i < n && source[i] == target[i])
            {
                i++;
            }
            if (i == n)
            {
                return 0;
            }

            long long minCost = -1;
            for (auto &p : canMap[i])
            {
                int mapBegin = p >> 32;
                int srcId = p & 0xffffffff;
                if (mapBegin < begin)
                {
                    continue;
                }
                string src = numToStr[srcId];
                string dst = target.substr(mapBegin, src.size());
                if (!strToNum.count(dst))
                {
                    continue;
                }
                int dstId = strToNum[dst];
                long long cost = dists[srcId][dstId];
                if (cost == INT_MAX)
                {
                    continue;
                }
                long long nextCost = dfs(mapBegin + src.size());
                if (nextCost == -1)
                {
                    continue;
                }
                cost += nextCost;
                if (minCost == -1 || cost < minCost)
                {
                    minCost = cost;
                }
            }
            return minCost;
        };
        return dfs(0);
    }
};